/*
 * BinaryTree.c
 *
 *  Created on: 07/07/2012
 *      Author: marcio
 */

#include "BinaryTree.h"

BinaryTreeNode* binarytreenode_newNode(void* elem){
	BinaryTreeNode* node = malloc(sizeof(BinaryTreeNode));
	node->elem = elem;
	node->left = NULL;
	node->right = NULL;
	node->lvl = -1;
	return node;
}

int binarytreenode_addToRight(BinaryTreeNode* root, BinaryTreeNode* newnode){
	if(root == NUll) return -1;
	if(root->right != NULL) return 1;
	root->right = newnode;
	root->right->lvl = root->lvl + 1;
	return 0;
}

int binarytreenode_addToLeft(BinaryTreeNode* root, BinaryTreeNode* newnode){
	if(root == NUll) return -1;
	if(root->left != NULL) return 1;
	root->left = newnode;
	root->left->lvl = root->lvl + 1;
	return 0;
}

BinaryTree* binarytree_newBinaryTree(BinaryTreeNode* root, int (*choice)(void*, void*)){
	BinaryTree* bt = malloc(sizeof(BinaryTree));
	bt->f = choice;
	bt->height = 0;
	bt->root = root;
	bt->size = 1;
	return bt;
}

int tree_getSize(BinaryTree* b){
	return b != NULL ? b->size : 0;
}

BinaryTreeNode* binarytree_getRoot(BinaryTree* b){
	return b != NULL ? b->root : NULL;
}

int binarytree_addNode(BinaryTree* b, BinaryTreeNode* newnode){
	if(newnode == NULL) return 1;
	BinaryTreeNode* v = b->root;
	BinaryTreeNode* father = NULL;
	while(v != NULL){
		father = v;
		if(b->f(v->elem, newnode) >= 0){
			v = v->left;
		}
		else v = v->right;
	}
	if(father->left = v)binarytreenode_addToLeft(father, newnode);
	else binarytreenode_addToRight(father, newnode);
	b->size++;
	return 0;
}

int binarytree_removeNode(BinaryTree* b, int (*test)(void*)){
	//TODO
	return 0;
}


BinaryTreeNode** binarytree_BFS(BinaryTree* b, long* size){
	*size = 0;
	BinaryTreeNode** nodes = malloc(sizeof(BinaryTreeNode)*b->size);
	BinaryTreeNode* current = b->root;
	Queue* q =  queue_newQueue();
	queue_add(q, (void*)current);
	while(!queue_isEmpty(s)){
		current = queue_push(s);
		nodes[(*size)++] = current;
		if(current->left != NULL) queue_add(s, current->left);
		if(current->right != NULL) queue_add(s, current->right);
	}
	return nodes;
}

BinaryTreeNode** binarytree_DFS(BinaryTree* b, long* size){
	*size = 0;
	BinaryTreeNode** nodes = malloc(sizeof(BinaryTreeNode)*b->size);
	BinaryTreeNode* current = b->root;
	Stack* s =  stack_newStack();
	stack_add(s, (void*)current);
	while(!stack_isEmpty(s)){
		current = stack_push(s);
		nodes[(*size)++] = current;
		if(current->left != NULL) stack_add(s, current->left);
		if(current->right != NULL) stack_add(s, current->right);
	}
	return nodes;
}

BinaryTreeNode** binarytree_BFSOnlyLeafs(BinaryTree* b, long* size){
	*size = 0;
	BinaryTreeNode** nodes = malloc(sizeof(BinaryTreeNode)*b->size);
	BinaryTreeNode* current = b->root;
	Queue* q =  queue_newQueue();
	queue_add(q, (void*)current);
	while(!queue_isEmpty(q)){
		current = queue_push(q);
		if(current->left != NULL) queue_add(q, current->left);
		if(current->right != NULL) queue_add(q, current->right);
		if(current->left == NULL && current->right == NULL) nodes[(*size)++] = current;
	}
	return nodes;
}

BinaryTreeNode** binarytree_DFSOnlyLeafs(BinaryTree* b, long* size){
	*size = 0;
	BinaryTreeNode** nodes = malloc(sizeof(BinaryTreeNode)*b->size);
	BinaryTreeNode* current = b->root;
	Stack* s =  stack_newStack();
	stack_add(q, (void*)current);
	while(!stack_isEmpty(s)){
		current = stack_push(s);
		if(current->left != NULL) stack_add(s, current->left);
		if(current->right != NULL) stack_add(s, current->right);
		if(current->left == NULL && current->right == NULL) nodes[(*size)++] = current;
	}
	return nodes;
}

int binarytree_BFSModify(BinaryTree* b,int (f)(void*)){
	BinaryTreeNode* current = b->root;
	Queue* q =  queue_newQueue();
	queue_add(q, (void*)current);
	while(!queue_isEmpty(q)){
		current = queue_push(q);
		f(current->elem);
		if(current->left != NULL) queue_add(q, current->left);
		if(current->right != NULL) queue_add(q, current->right);
	}
	return 0;
}

int binarytree_DFSModify(BinaryTree* b,int (f)(void*)){
	BinaryTreeNode* current = b->root;
	Stack* s =  stack_newStack();
	stack_add(s, (void*)current);
	while(!stack_isEmpty(s)){
		current = stack_push(s);
		f(current->elem);
		if(current->left != NULL) stack_add(s, current->left);
		if(current->right != NULL) stack_add(s, current->right);
	}
	return 0;
}
